
import java.util.*;
import java.lang.Math.*;

public class scount{

    public static long scount(Graph g, double eta) {
//        List<Long> l = new ArrayList<Long>();
//        for (int i = 0; i < 7; i++){
//             l.add( new Long(run(g,eta)));
//        }
//        Collections.sort(l);
//        return l.get(3);
          return run(g,eta);
    }


    public static long run(Graph g, double eta){

      // generate 75 * eta^(-2) * m^2 samples
      AllMatchMC mc = new AllMatchMC(g,eta);
      mc.setMixingTime(eta);

      // numSamples was originally 
      int m = g.edges.size();
      int numSamples = (int)(75 * m * (1.0/Math.pow(eta,2)));
      //int numSamples = (int)(75 * m * Math.log(m) * (1.0/Math.pow(eta,2)));
      //int numSamples = (int)(75 * (Math.sqrt(m * Math.log(m))) * Math.log(m) * (1.0/Math.pow(eta,2)));
      int mixingTime = mc.getMixingTime();
      int relaxTime = mc.getRelaxedMixingTime();
//      System.out.println("# of samples = " + numSamples);
//      System.out.println("mixing time =  " + mixingTime);
//      System.out.println("relaxed time = " + relaxTime);

      // keeps running count of those crazy ratios
      double ratio = 1.0;

      int[] edgeSamples = new int[g.edges.size()]; 

      for (int i = 0; i < numSamples; i++){
          int j = 0;
          Set<Edge> removedEdges = new HashSet<Edge>();
          Set<Edge> s = mc.randomSample(eta);

          for (Edge e : g.edges){
              removedEdges.add(e);
              if (!containsAny(s,removedEdges)){
                  edgeSamples[j]++;
              }
              j++;
          }
      }



      /*LinkedList<Set<Edge>> samples = mc.generateSamples((int)(75 * g.edges.size() * Math.pow(eta, -2)), eta);


      // keep track of edges removed in the current step and the last
      // current is numerator, last is denominator
      Set<Edge> removedEdgesCurrent = new HashSet<Edge>();
      Set<Edge> removedEdgesLast = new HashSet<Edge>();

      for (Edge e : g.edges){
          removedEdgesCurrent.add(e);
          int current = 0, last = 0;

          for (Set<Edge> s : samples){
              // if sample contains any edges in the removed set, don't count it
              if (!containsAny(s,removedEdgesCurrent)){
                  current++;
                  last++;
              }
              else if (!containsAny(s,removedEdgesLast)){
                  last++;
              }
          }          
          removedEdgesLast.add(e);
          ratio *= (double)current/(double)last;
      }*/

      ratio *= (double)edgeSamples[0]/(double)numSamples;
 //         System.out.println("0: " + edgeSamples[0] + " || num: " + numSamples);
      for (int j = 1; j < edgeSamples.length; j++){

  //        System.out.println("j: " + edgeSamples[j] + " || j-1: " + edgeSamples[j-1]);
          if (edgeSamples[j] <= 0){
            break;
          }
             
          ratio *= (double)edgeSamples[j]/(double)edgeSamples[j-1];
      }
          
   //   System.out.println("ratio: " + ratio + " || count: " + Math.pow(ratio,-1) + "\n");
      

      return (long)(.5 + (1.0 / ratio));
    }

    // if the set a contains any element of set o, then return true
    public static boolean containsAny(Set<?> a, Set<?> o){
        for (Object t: o){
            if (a.contains(t)){
               return true;
            }
        }
        return false;
    } 
}



